import java.util.*;

/**
 * @author LKQ
 * @date 2021/12/25 19:25
 * @description 思路可以，但是无法AC，超过时间限制
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {-1, 0, 1, 2, -1, -4};
        solution.threeSum(nums);
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length < 3) {
            return list;
        }
        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = nums[i] + nums[j];
            }
        }
        Map<Integer, Integer> a = new HashMap<>();
        for (int value: nums) {
            if (!a.containsKey(value)) {
                a.put(value, 1);
            }else {
                a.put(value, a.get(value)+1);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                Map<Integer, Integer> copyA = new HashMap<>(a);
                boolean canBe = true;
                List<Integer> temp = new ArrayList<>();
                if ( a.containsKey(-dp[i][j])) {
                    temp.add(nums[i]);
                    temp.add(nums[j]);
                    temp.add(-dp[i][j]);
                }
                for (Integer integer: temp) {
                    if (copyA.containsKey(integer)) {
                        copyA.put(integer, copyA.get(integer)-1);
                    }
                    if (copyA.get(integer) < 0) {
                        canBe = false;
                        break;
                    }
                }
                if (!canBe) {
                    continue;
                }
                temp.sort(new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o1 - o2;
                    }
                });
                if (!list.contains(temp) && !temp.isEmpty()) {
                    list.add(temp);
                }
            }
        }
        return list;
    }
}
